package org.example.sword2offer.primary;

import java.util.ArrayList;

/**
 * @author: lynn
 * @Descript:最小的k个数
 * 输入n个整数，找出其中最小的K个数。
 * 例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4
 * D:\BaiduNetdiskDownload\Java，C++算法与数据结构【更多精品教材：www.hegoubbs.com】\三 40:00
 * 考点：快速排序，找出 partition，分割点
 * @date: 2021/3/14 1:17
 * @version: 1.0
 */
public class Q29_GetLeastKNumbers_H {
    public static void main(String[] args) {
        int[] arr = {4,5,1,6,2,7,3,8};
        int k=3;
        ArrayList<Integer> res=GetLeastNumbers(arr,k);
        System.out.printf(""+res);
    }

    public static ArrayList<Integer> GetLeastNumbers(int [] input, int k) {

        ArrayList<Integer> res = new ArrayList<Integer>();
        if(k>input.length||k<=0){
            //一般是不会直接抛出异常的，这一步在牛客网上调试了好久
            return res;
        }
        sort(input,0,input.length-1);
        for (int i = 0; i <k ; i++) {
            res.add(input[i]);
        }
        return res;
    }

    //快速排序，选择基准点分治排序，算法复杂度O(nlogn),极端情况下退化为 O(n*n)
    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void sort(int[] arr, int l, int r){
        if( l >= r )
            return;
        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }
    //如何找到partition
    private static int partition(int[] arr, int l, int r){
        int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
        for( int i = l + 1 ; i <= r ; i ++ )
            if( arr[i] <arr[l] ){
                j ++;
                swap(arr, j, i);
            }
        swap(arr, l, j);
        return j;
    }
    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
